#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int mod=998244353;
int qpow(int a,int n)
{
    int ret=1;
    while(n)
    {
        if(n&1)ret=ret*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ret;
}
void test()
{
    cout<<qpow(5,3);
}
void solve()
{
    int n,q;
    n=read(),q=read();
    vector<int>v(n+1);
    vector<vector<int>>dp(21,vector<int>(n+1));
    for(int i=1;i<=n;i++)
    {
        v[i]=read();
        //dp[0][i]=(dp[0][i-1]+(v[i]*v[i]%mod))%mod;
    }
    for(int i=1;i<=20;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=(dp[i][j-1]+qpow(v[j],i))%mod;
        }
    }

    for(int i=1;i<=q;i++)
    {
        int x,l,r,k;
        cin>>x;
        if(x==1)
        {
            l=read(),r=read();
            cout<<(dp[1][r]-dp[1][l-1]+mod)%mod<<endl;
        }
        else if(x==2)
        {
            l=read(),r=read(),k=read();
            cout<<(dp[k][r]-dp[k][l-1]+mod)%mod<<endl;
        }
        else 
        {
            l=read(),r=read();
            int x=(dp[2][r]-dp[2][l-1]+mod)%mod;
            int z=(dp[1][r]-dp[1][l-1]+mod)%mod;
            cout<<(((r-l+1)*x)%mod-((z*z)%mod)+mod)%mod<<endl;
        }
    }
}
signed main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}